package com.practice.sequence;

import java.util.Arrays;

/**
 * A rigorous teacher makes all his students stand in a line before entering 
 * the classroom. Being a rigorous teacher, he makes the students line up in 
 * non-descending order by height. One time, while the students were lining up, 
 * the teacher had to go to the bathroom. The students took the opportunity to 
 * play with the teacher's head and make a crazy line. They defined the 
 * craziness of a line as the sum of the absolute difference in height between 
 * each pair of consecutive students. Since a line ordered by height has 
 * minimum craziness, they of course decided to arrange themselves in a line 
 * with maximum craziness.
 * 
 * You are given a int[] heights, where each element is the height of a single 
 * student. Return the maximum possible craziness of a line made by those 
 * students. 
 * 
 * http://www.topcoder.com/stat?c=problem_statement&pm=10926&rd=14239
 */
public class CrazyLine {
	public int maxCrazyness(int[] h) {
		Arrays.sort(h);
		int N = h.length;
		int n = N / 2;
		int max = 0;
		if (N%2 == 0) {
			for (int i=0; i<n-1; i++) {
				max += 2 * (h[N-1-i] - h[i]);
			}
			max += h[n] - h[n-1];
			return max;
		}
		else {
			for (int i=0; i<n; i++) {
				max += 2 * (h[N-1-i] - h[i]);
			}
			return Math.max(max + h[n] - h[n+1], max + h[n-1] - h[n]);
		}
	}
}
